package main

import "fmt"

//给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
//
//说明：每次只能向下或者向右移动一步。

// 状态转移方程 dp(i,j) = min(dp[i][j-1] , dp[i-1][j]) + grid[i][j]
// 执行用时： 8ms 内存消耗： 4.4Mb
func minPathSum(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	if m == 0 {
		return 0
	}
	dp := make([][]int, m)
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
		for j := 0; j < n; j++ {
			if i == 0 && j == 0 {
				dp[i][j] = grid[i][j]
				continue
			}
			if i == 0 {
				dp[0][j] = dp[0][j-1] + grid[i][j]
				continue
			}
			if j == 0 {
				dp[i][0] = dp[i-1][0] + grid[i][j]
				continue
			}
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
		}
	}
	return dp[m-1][n-1]
}

// 执行用时： 8ms 内存消耗： 4.4Mb
func minPathSum2(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	if m == 0 {
		return 0
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i == 0 && j == 0 {
				continue
			}
			if i == 0 {
				grid[0][j] = grid[0][j-1] + grid[i][j]
				continue
			}
			if j == 0 {
				grid[i][0] = grid[i-1][0] + grid[i][j]
				continue
			}
			grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
		}
	}
	return grid[m-1][n-1]
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func main() {
	pathArr := [][]int{
		{1, 3, 1},
		{1, 5, 1},
		{4, 2, 1},
	}

	sum := minPathSum(pathArr)
	fmt.Println("ret : = ", sum)
}
